#include <bits/stdc++.h>
using namespace std;

/*
面试题 02.01. 移除重复节点
已解答
简单
相关标签
premium lock icon
相关企业
提示
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1：

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]
示例2：

 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]
提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：

如果不得使用临时缓冲区，该怎么解决？
*/

// 法一
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        // 空链表为nullptr 
        if (head == nullptr)    return nullptr;

        // 哈希集合存储已经出现的节点值 快速查重
        unordered_set<int> seen;
        // 遍历cur指针 从head开始
        ListNode* curr = head;
        // 记录当前val
        seen.insert(curr->val);

        // 迭代 处理后续节点 
        while (curr->next != nullptr) {
            ListNode* nextNode = curr->next;
            if (seen.count(nextNode->val)) {
                // val seen  跳过node
                curr->next = nextNode->next;
            } else {
                // 若值未出现 加入集合 move 指针
                seen.insert(nextNode->val);
                curr = curr->next;
            }
        }
        return head;
    }
};

// 法二
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        // 边界处理：空链表直接返回
        if (head == NULL) {
            return NULL;
        }
        
        // 利用节点值范围（0-20000）创建数组替代哈希表，空间换时间，查询更快
        bool hash[20001] = {0};
        ListNode* tmp = head;       // tmp：跟踪结果链表的尾部（用于拼接不重复节点）
        ListNode* curr = head->next;// curr：遍历原链表的当前节点
        // 标记头节点的值为已出现（头节点一定保留）
        hash[head->val] = 1;
        
        // 遍历后续节点
        while (curr) {
            if (!hash[curr->val]) { // 当前节点值未出现过
                hash[curr->val] = 1; // 标记为已出现
                tmp->next = curr;    // 接入结果链表
                tmp = tmp->next;     // 移动结果链表尾部指针
            }
            // 无论是否重复，都移动到下一个节点（重复节点会被自然跳过）
            curr = curr->next;
        }
        
        // 截断结果链表尾部，避免残留原链表的重复节点
        tmp->next = NULL;
        return head;
    }
};

// 法三
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        // 边界处理：空链表或仅1个节点，无重复可删
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        // 外层指针：基准节点（保留首次出现的节点，依次后移）
        ListNode* base = head;
        while (base != nullptr) {
            // 内层指针：prev跟踪当前检查节点的前一个，curr遍历后续节点
            ListNode* prev = base;   // 初始为基准节点（后续节点的前驱）
            ListNode* curr = base->next; // 从基准节点的下一个开始检查
            while (curr != nullptr) {
                if (curr->val == base->val) {
                    // 找到重复节点：跳过curr（删除重复）
                    prev->next = curr->next;
                } else {
                    // 非重复节点：prev后移，继续跟踪
                    prev = curr;
                }
                // 无论是否删除，curr都后移（遍历下一个节点）
                curr = curr->next;
            }
            // 基准节点后移，处理下一个待检查的节点
            base = base->next;
        }
        
        return head;
    }
};